class Solution:
    def combine(self, n: int, k: int):
        n_list = [i for i in range(1, n+1)]
        self.res = []
        self.add_item([], n_list, k)
        return self.res

    def add_item(self, mid_res, mid_list, k):
        if k == 1:
            for num in mid_list:
                mid = mid_res[:]
                mid.append(num)
                self.res.append(mid)
            return
        mid2 = mid_list[:]
        for num in mid_list:
            mid = mid_res[:]
            mid.append(num)
            mid2.remove(num)
            self.add_item(mid, mid2, k-1)


class Solution2:
    def combine(self, n: int, k: int):
        self.n_list = [i for i in range(1, n + 1)]
        res = self.add_item(k)
        return res

    def add_item(self, k):
        if k == 1:
            return [[i] for i in self.n_list]
        return [i + [j] for i in self.add_item(k-1) for j in self.n_list if j > i[-1]]


if __name__ == '__main__':
    a = Solution2()
    print(a.combine(4, 3))
